BOJ_5670_휴대폰 자판

트라이(Trie) 자료구조를 활용해서 자동 입력을 구현하는 문제

첫 입력은 항상 존재하고, 이후 다음 노드의 자식이 1개 뿐이라면, 입력하지 않아도 자동으로 작성된다
이를 구현하기 위해 트라이 자료구조의 search 메소드를 적절하게 변경해줬다

문제 자체는 어렵진 않지만 까다로운 포인트가 있다

1. 테스트 케이스 수가 정해지지 않았다
   그래서 입력이 얼마나 들어올지 몰라, try catch를 사용해서 입력을 받았다

2. 출력이 고정 소수점 2자리이다
   처음에 틀려서 확인해봤더니 파이썬에서는 round() 를 썼을 때 2.00 이 아닌 2.0으로 나오고 있었다...!
   print(round(count / N, 2)) 이렇게 작성하던 걸
   print(f'{count / N:.2f}') 이렇게 포맷팅 해주었다

# 트라이를 활용하는 문제  
# search 로직을 조금 변경해주면 된다!  
# 입력 테스트 케이스 수 가 정해지지 않아서 try catch로 처리했다  
  
import sys  
  
  
class Node(object):  
    def __init__(self, key, data=None):  
        self.key = key  
        self.data = data  
        self.children = dict()  
  
  
class Trie:  
    def __init__(self):  
        self.head = Node(None)  
  
    def insert(self, string):  
        current_node = self.head  
  
        for char in string:  
            if char not in current_node.children:  
                current_node.children[char] = Node(char)  
            current_node = current_node.children[char]  
        current_node.data = string  
  
    def search(self, string):  
        current_node = self.head  
        count = 0  
  
        for i in range(len(string)):  
            char = string[i]  
            # print('now char : ', char)  
            # print('children : ', current_node.children.keys())            if i == 0:  
                count += 1  
            elif len(current_node.children) > 1 or current_node.data:  
                count += 1  
  
            current_node = current_node.children[char]  
        return count  
  
  
def solution(N, strings):  
    trie = Trie()  
    string_list = strings  
    for string in string_list:  
        trie.insert(string)  
  
    count = 0  
    for string in string_list:  
        count += trie.search(string)  
  
    print(f'{count / N:.2f}')  
  
  
def solution_main():  
    while True:  
        try:  
            N = int(sys.stdin.readline())  
            if not N:  
                break  
            strings = [sys.stdin.readline().strip('\n') for _ in range(N)]  
            solution(N, strings)  
        except:  
            break  
  
  
solution_main()